如何帮助拜登获得连任？

引言

2024 年美国总统大选进入新阶段。3 月 4 日，美国最高法院推翻了科罗拉多州阻止唐纳德·特朗普参加该州 2024 年总统初选的裁定。在随后的“超级星期二”以及佐治亚等三个州的初选中，现任民主党总统乔·拜登和前共和党总统唐纳德·特朗普均大获全胜，获得各自政党的提名，成为参选总统的候选人。这意味着，两人将在 11 月的大选中再次对决。

图 1: 美国现任总统拜登和前任总统特朗普

美国总统是由选民普选叠加赢家通吃的选举人制度产生^[1]。每个州的选举人票数是由其在国会参议院和众议院的席位数决定。美国有 50 个州，每个州有两票参议院选举人票（共 100 票）和依照各州人口比例分配的众议院选举人票（共 435 票），加上华盛顿特区额外的 3 票，总共 538 票。在州级普选中获胜的总统候选人会获得该州的所有选举人票，最终获得超过半数选举人票（即 270 票及以上）的候选人当选为总统。

图 2: 2020 年美国总统大选结果

虽然目前拜登竞选资金充足，但其连任前景并不明朗。在 2020 年的总统大选中，拜登以 306 张选举人票胜出，但他与特朗普在普选票上的差距并不大（图 2）^[2]。拜登上任后取消了一系列打击非法移民的政策，导致非法移民数量迅速上升，特朗普和共和党借此猛烈批评拜登。同时，拜登的年龄和健康问题也成为焦点，超过 60% 的选民对此表示担忧。作为回应，拜登及其团队则强调民主价值，将特朗普对 2020 年选举结果的质疑和对国会暴乱的煽动描述为严重的叛乱。拜登还批评特朗普对乌克兰的立场等，意在唤起民众对民主的支持。尽管如此，当前民调显示，拜登普遍不如特朗普受欢迎，公众对其政策的态度也较为消极^[3]。甚至马斯克在 3 月 25 日也明确表示不再支持民主党，并声称美国需要“红色浪潮”，否则会完蛋！

问题

假如你是韩霉霉，你的好朋友乔·拜登正在寻求 2024 年总统大选连任。为此，拜登竞选团队计划在全美开展系列巡回竞选活动。各州竞选活动所需时间将根据人口规模确定，每一千万人口至少分配一天（图 3）。

图 3: 各州活动所需天数及近六次大选的摇摆州

由于拜登总统需定期回到白宫处理事务，巡回竞选活动将分轮次进行。每一轮次，拜登将乘坐专机从华盛顿出发，按照计划访问几个州后返回。考虑到拜登的年龄，规划行程时需避免在飞行日安排竞选活动，并尽量缩短飞行总距离以减少疲劳。基于这些考量，请为你的好朋友拜登规划合理的行程，需要考虑以下两种情况：

1. 在美国总统大选中，赢得摇摆州至关重要。如图 3 所示，2000-2020 年间的总统选举中出现过 21 个摇摆州^[4]。拜登竞选团队计划在这 21 个摇摆州开展巡回竞选活动。如果每轮次活动最多持续两周，该如何规划行程？若希望分 3 轮次完成，并且每轮次的持续时间大致相同，应如何安排？

2. 考虑到离大选还有半年多时间，为了万无一失，拜登竞选团队计划在全美 48 个本土州进行巡回竞选活动。如果每轮次的活动最多持续一个月，该如何规划行程？若希望分 3 轮次完成，且每个轮次的持续时间大致相同，应如何安排？

需要注意的是，以上每轮次的时间限制不包括该轮次最后一天返回华盛顿的飞行时间。

模型

问题涉及拜登竞选团队分若干轮次访问所有摇摆州或全美本土州，并力求最小化总飞行距离。每个州的竞选活动都需要一定时间，而每个轮次的总时间也有上限。这本质上是一个具有容量限制的车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）^[5]。在 CVRP 问题中，任务是由一组车辆将货物从仓库运输到预定客户点，每个客户点有固定的货物需求量，且每个客户点只能由一辆车访问一次。所有车辆从同一仓库出发，访问完所有客户点后返回仓库（图 4）。所有车辆的容量相同，不同路线的行驶成本不同，问题的目标是最小化总行驶成本。

图 4: 有容量限制的车辆路径问题

在拜登团队面临的问题中，每个州对应 CVRP 问题中的客户点，华盛顿则相当于仓库。州的访问天数相当于客户点的货物需求，轮次数则相当于车队的车辆数量，而专机飞行距离类似于 CVRP 问题中的车辆行驶距离。本文用节点集  = {1, 2, , } 表示需要访问的  个州，节点 0 表示华盛顿。 表示第  个州所需天数（= 活动所需的天数 + 额外的一天飞行时间）， 表示每一轮次的最大持续天数,  表示轮次数。 表示节点  和  之间的飞行距离，可通过球面距离公式计算：其中  为地球半径， 和  表示第  个节点的纬度和经度。在对称的情况下，节点间的飞行距离不依赖于飞行方向，即  =  且  = 0。问题的一个可行解涉及两个方面：

• 将节点集  划分为  个子集 , , , ，并确保 , 。

• 对每一个节点集  有一个排序，以指定访问的顺序。

这个问题显然可以表示为一个无向完全图 ，由节点集  = ，边集 ，以及边权 ,    构成。在该图中，一个可行解是包含唯一共同节点 0 的  个环路。每个环路代表一个轮次的访问路径。若用  = 1 或 0 表示问题的解中是否包含经过节点  和  的路径，那么问题的目标函数（最小化总飞行距离）可以表述为：考虑到每个州节点必须恰好被访问一次，即与每个州节点相连的只有一进一出的两条边。因此有以下州节点约束：而对于节点 0（华盛顿），则必须与 2 条边与之相连，因为每个轮次开始和结束都在华盛顿，即有  次出发和  次返回。因此有以下零节点约束：然而，以上两条约束并不能确保环路满足容量限制，也不能排除不经过 0 节点的子环路。

图 5: 超出容量限制的环路和子环路

例如图 5 中，尽管所有环路都满足以上两个约束条件，但红色环路超出了容易限制，而绿色环路并没有经过 0 节点（这种环路称为子环路）。为此，需引入以下环路约束：其中  =  为访问州节点集  所需的最小轮次数。环路约束能够同时起到约束容量和消除子环路的作用。首先，上式约束规定了从任意节点集  出去的边不少于 2，这包含了容量相关的约束。例如图 5 中的红色环路的需求为 12，最小轮次数为 2，但从红色环路对应的节点集出去的边数仅为 2，小于 4，所以违反了上述环路约束。其次，环路约束是对任意州节点集来说都得遵守的约束，对于一条不经过起始点的子环路（例如图 5 中的绿色子环路），从由该环路节点构成的节点集引出去的边数为 0。而该节点集很显然所需最少轮次数不会小于 1，所以也违反了上述环路约束。因此，上式环路约束能够同时规避这两种不符合要求的环路。

综上所述，整个问题可以表述为以下的整数规划问题^[6]：在上述整数规划模型中，环路约束是任意州节点集都必需满足的。当需要访问的州数量较多时，环路约束的数量将显著增多，这会极大地增加整数规划问题求解的难度。在接下来两个不同规模的问题中，本文将采取不同的解决策略。

图 6: 摇摆州和本土州 TSP 问题的解

此外，值得注意的是，如果将轮次数  设置为 1，并将容量  设置得足够大，上述整数规划问题将退化为旅行商问题（Travelling Salesman Problem, TSP）。图 6 给出了仅访问摇摆州和访问所有本土州情形下的 TSP 问题的解。

问题一：仅访问摇摆州

问题一涉及 21 个摇摆州，前述整数规划模型理论上需要枚举出所有可能的环路节点集合，并为它们一一添加环路约束。这将引入大量的环路约束，使计算机很难在有限时间内给出问题的解。为了高效地消除不符合条件的环路，通常有两种解决策略^[5,7,8]：一种方法是将环路约束转化为复杂度较低的 Miller-Tucker-Zemlin（MTZ）约束；另一种方法是先忽略环路约束，形成原问题的松弛版本，然后采用分枝定界等算法进行求解。在算法的迭代过程中，根据当前节点松弛后线性规划模型（relaxed LP）的解来检查是否存在违反约束的环路。若存在  个违反约束的环路 , , , ，就向松弛问题中加入去除这些环路的约束：然后继续迭代算法，直至不再发现有违反约束的环路。换句话说，就是不预先加入针对所有可能环路的约束，而是在算法迭代过程中，出现不满足约束的环路时，再有针对性地加入约束。经过尝试，发现以上两种策略中的后一种效率更高，本研究据此采用第二种策略。图 6 给出了以第二种策略求解出来的 TSP 问题。

图 7: 每轮次不超 14 天访问摇摆州的最优方案

访问所有摇摆州需 52 天，如果要求每轮次的活动最多持续  = 14 天，则轮次数至少为  =  = 4。将  = 14 和  = 4 代入整数规划模型，并应用第二种策略来消除不符合条件的环路，求解结果如图 7 所示。模型给出的最优方案中，4 轮次的访问所需天数分别为 14、12、12 和 14 天，总飞行距离为 19096 公里。

图 8: 每轮次不超 13 天访问摇摆州的最优方案

为了使每轮次的访问天数尽量均匀，考虑到 52/4 = 13，将每轮次可用天数  调整为 13 天并重新进行模型求解，求解结果如图 8。模型给出的最优方案中，4 轮次的访问天数均为 13 天，总飞行距离为 20335 公里。与图 7 的方案相比，不难发现：通过下调  来使各轮次访问天数更均匀的同时，也会增加总的飞行距离。

图 9: 分 3 轮次访问摇摆州的最优方案

若计划用  = 3 轮次完成对 21 个摇摆州的访问，且每轮次的持续时间尽可能一致，那么平均每轮次需 52/3 = 17.33 天。因此，可以把每轮次的可用天数定为 18 天。将  = 18 和  = 3 代入模型求解，结果如图 9 所示。模型给出的最优方案中，3 轮次访问所需天数分别为 17、17 和 18 天，总飞行距离为 16995 公里。与图 7 和 8 的方案相比，减少轮次数的同时也会降低总飞行距离。

问题二：访问全美本土州

问题二将访问范围从 21 个摇摆州扩大到全部 48 个本土州。问题一中用于消除不合规环路的策略，因节点数量大幅增多而难以在有限时间内找到最优解。为此，本文通过以下两个步骤得到问题的可行解：

• 节点聚类：根据州节点间的距离和每轮次可用天数  对州节点进行聚类，将节点集  划分为  个子集 , , , 。这里的“节点子集”在有些文献中也被称为“点簇”或“集群”。

• 路径规划：对每一个节点子集  应用之前消除不合规环路的方法解决 TSP 问题，以寻找访问该子集内所有节点的最短路径。

值得注意的是，通过以上两个步骤获得的解可能不是全局最优解，解的质量在很大程度上依赖于节点聚类的效果。本文通过以下步骤对节点进行初步聚类^[9]：

1. 以距离起点（华盛顿）最远的州节点作为起始，创建第一个节点子集。

2. 迭代地向子集中加入新的州节点。每次选取与当前子集内节点平均位置最近的节点。即，第二个加入的节点与第一个最近的，第三个加入的节点是与前两个平均位置最近的，以此类推。当加入距离最近的节点将超出容量  时，尝试加入距离次近的节点，直到无法再加入新节点为止。

3. 一旦无法向当前子集添加新节点而不超出容量  时，则停止加入，并以最接近当前子集平均位置的节点作为新子集的起点，跳至第 2 步。

经以上初步聚类后形成  个节点子集后，可进一步调整和优化这些子集：尝试将某个子集中的节点重新分配到其他子集，如果这样做使得该节点更接近新子集的平均位置，且不会使新子集超过容量限制，那么接受调整，并继续进行此类尝试，直至没有更多的调整可能。

图 10: 每轮次不超 30 天访问本土州的最优方案

接下来本文将应用上述策略处理问题二，要求访问所有 48 个本土州，这将需要 111 天。若要求每轮次的活动最多持续  = 30 天，则轮次数至少为  =  = 4。将  = 30 代入模型，求解结果如图 10。得到的方案中，4 轮次访问天数分别为 29、27、29、26 天，总飞行距离 24198 公里。

图 11: 每轮次不超 28 天访问本土州的最优方案

如果想让每轮次的访问天数尽量均匀，考虑到 111/4 = 27.75，可将每轮次可用天数  调整为 28 天后重新求解，结果如图 11。得到的新方案中，4 轮次的访问天数分别为 27、28、28 和 28 天，总飞行距离达 26494 公里。与前一方案相比，均衡天数的同时略增总飞行距离。

图 12: 分 3 轮次访问本土州的最优方案

若计划用  = 3 轮次完成对 48 个本土州的访问，且每轮次的持续时间尽可能一致，那么可以把每轮次的可用天数定为 37。将  = 37 代入模型求解，结果如图 12，得到 3 轮次访问所需天数均为 37 天，总飞行距离为 23833 公里。与图 10 和 11 的方案相比，减少轮次数的同时也会降低总飞行距离。

结论

为了给拜登总统的巡回竞选活动策划一条高效的路线，本文以最小化总飞行距离为目标，将分轮次访问摇摆州和全美本土州的任务转化为 CVRP 问题，并据此构建了一个整数规划模型。考虑到问题的计算复杂性，针对访问 21 个摇摆州和 48 个本土州这两种不同规模的问题，本文采用了不同的策略，并成功地求得了优化方案。

在处理摇摆州访问任务时，通过动态加入环路约束的策略有效提高了求解效率；而对于访问全美本土州这个更大规模的任务，本文通过先节点聚类后路径规划的方法显著降低了计算复杂度。对于两种不同规模的问题，本文均给出了合理的时间分配和路线规划，确保了覆盖所有目标州的同时，最大程度地减少总飞行距离。针对不同的轮次持续时间要求，模型提供了多种可行方案。同时还比较了不同方案之间在时间均衡性和总飞行距离上的差异，为竞选团队提供了灵活的规划选项。

本文不仅为 2024 年美国总统巡回竞选活动提出了详细的规划建议，其采用的方法和策略也对高效处理不同规模的 CVRP 问题或相似问题提供了重要的参考。

附录

点击文章左下角“阅读原文”获取本文 PDF 版和附件。

参考资料

[1]

USAGov. How the president is elected, 2024: https://www.usa.gov/election

[2]

Wikipedia contributors. 2020 united states presidential election, 2024: https://en.wikipedia.org/wiki/2020_United_States_presidential_election

[3]

Chris Stein. Biden slightly behind trump but voters’ views of economy improve, poll shows, 2024: https://www.theguardian.com/us-news/2024/mar/13/biden-trump-economy-poll

[4]

Wikipedia. Swing state, 2024: https://en.wikipedia.org/wiki/Swing_state

[5]

数据工具箱. 有容量限制的车辆路径问题是什么, 2022: https://baijiahao.baidu.com/s?id=1736712661143043188

[6]

Ted Ralphs. Capacitated vehicle routing and some related problems, 2005: https://coral.ise.lehigh.edu/~ted/files/talks/CSE05.pdf

[7]

刘兴禄. Tsp 中两种不同消除子环路的方法及 callback 实现, 2022: https://blog.csdn.net/hsinglukliu/article/details/107848461

[8]

Austin Buchanan. Python codes for the traveling salesman problem and vehicle routing problem, 2022: https://github.com/AustinLBuchanan/TSP_VRP

[9]

MathWorks. Capacitated vehicle routing problem, 2023: https://www.mathworks.com/help/matlab/math/quantum-capacitated-vehicle-routing.html